#include <stdio.h>
#include <string.h>
#define N 100


//哈夫曼树由哈夫曼节点以及树的个数决定
struct T_Huffman {
    int treenum;//记录树的个数
    struct T_Node
    {
        char code[20];//记录从根节点到当前位置的哈夫曼码
        int w;//记录权值
        int parent;//记录父元素所在位置
        int lchild;//记录左孩子
        int rchild;//记录右孩子

    }huffmannode[2 * N];


}huffmantree;


void GetHuffmamCode(int w[], char  code[][20], int n);

void inihuffman(int w[], int n);

void merge();

void getcode(int root);

int main()
{
    int i;

    int w[] = { 1,2,4,8,16,32,64,128 };
    char code[8][20];
    GetHuffmamCode(w, code, 8);

    for (i = 0; i < 8;i++)
    {
        printf("%s\n", code[i]);
    }
    return 0;
}





//w[]是权值,code[][]用于存储哈夫曼码,n记录数据总量
//功能：题目所求函数，获取哈夫曼码
void GetHuffmamCode(int w[], char  code[][20], int n)
{
    int i;//计数器
    inihuffman(w, n);//初始化哈夫曼树

    //每次循环将合并两个森林中的树。从n棵树合并成只剩一棵树总共需要n-1次操作
    for (i = 0;i < n - 1;i++) {
        merge();
    }
    //将'\0'先放入字符数组中，使之成为字符串
    strcpy(huffmantree.huffmannode[2 * n - 2].code, "");

    //获取哈夫曼码
    getcode(2 * n - 2);

    //把哈夫曼码存到指定数组当中
    for (i = 0;i < n;i++) {
        strcpy(code[i], huffmantree.huffmannode[i].code);
    }

}


//w[]是权值,n记录数据总量
//功能：初始化哈夫曼树
void inihuffman(int w[], int n) {
    int i;//计数器
    for (i = 0; i < n; i++)
    {
        huffmantree.huffmannode[i].parent = -1;//初始化父元素为-1，即当前节点为根节点(森林的树中的一个)
        huffmantree.huffmannode[i].w = w[i];//将权值从w[]中转移到节点中
        huffmantree.huffmannode[i].lchild = -1;
        huffmantree.huffmannode[i].rchild = -1;//初始均为根节点，无左右孩子
    }
    huffmantree.treenum = n;//共有n个节点 

}

//功能：找到两个权最小的树并合并
void merge() {
    int i;//计数器
    int t1, t2;//存储器

    t1 = -1;
    //遍历最初森林里的根节点们
    for (i = 0;i < huffmantree.treenum;i++)
    {
        //寻找为根节点的节点
        if (huffmantree.huffmannode[i].parent == -1) {
            //寻找权最小的节点
            if (t1 == -1 || huffmantree.huffmannode[i].w < huffmantree.huffmannode[t1].w)
            {
                //找到目前权值最小的节点并存储在t1中
                t1 = i;
            }
        }
    }

    t2 = -1;
    //遍历最初森林里的根节点们
    for (i = 0;i < huffmantree.treenum;i++)
    {
        //寻找为根节点的节点
        if (huffmantree.huffmannode[i].parent == -1) {
            //寻找除却t1以外权最小的节点
            if (i != t1 && (t2 == -1 || huffmantree.huffmannode[i].w < huffmantree.huffmannode[t1].w))
            {
                //找到目前权值最小的节点并存储在t2中
                t2 = i;
            }
        }
    }


    //核心步骤 ***操作哈夫曼树进行合并

    //合并两棵树，将新树的孩子节点与原节点的父节点赋值完毕
    huffmantree.huffmannode[huffmantree.treenum].lchild = t2;
    huffmantree.huffmannode[huffmantree.treenum].rchild = t1;
    huffmantree.huffmannode[t1].parent = huffmantree.huffmannode[t2].parent = huffmantree.treenum;

    //新树的权值为两树之和
    huffmantree.huffmannode[huffmantree.treenum].w = huffmantree.huffmannode[t1].w + huffmantree.huffmannode[t2].w;

    //新树无父节点
    huffmantree.huffmannode[huffmantree.treenum].parent = -1;

    //哈夫曼内含树的数量++
    huffmantree.treenum++;








}


//root 是当前哈夫曼树根节点所在的下标
//功能：将从根节点到当前节点的哈夫曼码放入code字符数组当中
void getcode(int root) {
    int t1, t2;


    //如果有左孩子，就在左孩子的code中加一个0
    //如果有右孩子，就在右孩子的code中加一个1
    if (huffmantree.huffmannode[root].lchild != -1)
    {
        t1 = huffmantree.huffmannode[root].lchild;
        //继承根节点的路径
        strcpy(huffmantree.huffmannode[t1].code, huffmantree.huffmannode[root].code);
        //在后面加个0
        strcat(huffmantree.huffmannode[t1].code, "0");
        //递归调用
        getcode(t1);

    }
    if (huffmantree.huffmannode[root].rchild != -1) {
        t2 = huffmantree.huffmannode[root].rchild;
        //继承根节点的路径
        strcpy(huffmantree.huffmannode[t2].code, huffmantree.huffmannode[root].code);
        //在后面加个1
        strcat(huffmantree.huffmannode[t2].code, "1");
        //递归调用
        getcode(t2);
    }


}




/*
第二十一题
设计一个函数
    void GetHuffmamCode(int w[], char  code[][20], int n)
w是一个整数数组，长度为n，表示第0个字符至第n-1个字符这n个字符的概率权值。该函数是求出这n个字符的哈夫曼编码，置于code数组中。要求将树的左分支标记为0，右分支标记为1。
（任何一个非叶子结点的左孩子结点权值小于等于右孩子结点的权值）
如下main函数执行后
int main(int argc, _TCHAR* argv[])
{
    int i;

    int w[]={1,2,4,8,16,32,64,128};
    char code[8][20];
    GetHuffmamCode( w, code, 8);

    for(i = 0; i < 8;i++)
    {
        printf("%s\n", code[i]);
    }
    return 0;
}
得如下结果：
0000000
0000001
000001
00001
0001
001
01
1
*/


